Bellman-Ford Algorithm
The Bellman-Ford Algorithm finds shortest paths from a given source to all vertices of the graph. Unlike Dijkstra’s Algorithm, it works well even for the graphs having negative weight edges.
Time Complexity: O(|V||E|)
.
Application: This algorithm can be used for detecting negative weight cycle in the graph regardless of the src
node.
Note: If the graph contains a negative weight cycle, shortest path for any vertex that contains the cycle looses its meaning as we can shorten path length as many times as we want by repeating the cycle again and again.
Pseudo code for Bellman-Ford Algorithm:
References: GeeksforGeeks, MIT video lecture